#include"tree.h"
#include"Queue.h"
void preOrder(BTNode* root) {
	if (root == NULL) {
		return;
	}
	printf("%d ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}
void inOrder(BTNode* root) {
	if (root == NULL) {
		return NULL;
	}
	inOrder(root->left);
	printf("%d ", root->data);
	inOrder(root->right);
}
void postOrder(BTNode* root) {
	if (root == NULL) {
		return NULL;
	}
	postOrder(root->left);
	postOrder(root->left);
	printf("%d ", root->data);
}
BTNode* BinaryFind(BTNode* root, BTDataType x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->data == x) {
		return root;
	}
	BTNode* leftN = BinaryFind(root->left, x);
	if (leftN) {
		return leftN;
	}
	BTNode* rightN = BinaryFind(root->right, x);
	if (rightN) {
		return rightN;
	}
	return NULL;
}
int BinaryTreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	 }
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelSize(BTNode* root,int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelSize(root->left,k-1) + BinaryTreeLevelSize(root->right,k-1);
}
int BinaryTreeDepth(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int leftD = BinaryTreeDepth(root->left);
	int rightD = BinaryTreeDepth(root->right);
	return leftD > rightD ? leftD + 1 : rightD + 1;
}
void BinaryDestroy(BTNode** root) {
	if (*root == NULL) {
		return;
	}
	BinaryDestroy((*root)->left);
	BinaryDestroy((*root)->right);
	free(*root);
	*root = NULL;
}
void levelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (root->left) {
			QueuePush(&q, root->left);
		}
		if (root->right) {
			QueuePush(&q, root->right);
		}
	}
	QueueDestroy(&q);
}

bool treeCompelet(BTNode* root) {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL) {
			break;
		}
		QueuePush(&q,root->left);
		QueuePush(&q,root->right);
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL) {
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}